package 回溯;

import java.util.*;

public class 回溯经典模板代码 {

    public static void main(String[] args) {
        // 栈式的选择及回退，
        Deque<Integer> path = new LinkedList<>();
        path.addLast(1);
        path.addLast(2);
        path.addLast(3);
        path.removeLast();

        // 结果为其中一路径
        List<Integer> list = new ArrayList<>(path);
        System.out.println(list.toString());

    }


    /**
     * 经典回溯，List形态
     * 还有String形态的，都是异曲同工，有遇到再补充进来
     */
    List<List<Integer>> ans = new ArrayList<>();

    public void backtrack(List<Integer> chooses, List<Integer> track) {

        if (track.size() == 10) {//TODO 触发结束条件。一般路径是固定大小的，例如全排列
            ans.add(new ArrayList<>(track));// 注意要重新new再加入答案中
        }
        for (int choose : chooses) {
            if (choose == -1) {//TODO 剔除选择不合法的
                continue;
            }
            track.add(choose);
            //TODO 选择有可能是会变化哒，传递的可能是其他的信息，比如说某种下标，是互不相关的选择。或者是已选的不可再选，chooses需要维护
            backtrack(chooses, track);
            track.remove(track.size() - 1);//int类型是下标哟。 如果是Integer则是查找删除那种呢
        }


    }


}
